/*************************************************************************
	> File Name: quick_sort.cpp
	> Author: 
	> Mail: 
	> Created Time: Wed 07 Aug 2024 12:54:05 PM CST
 ************************************************************************/

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <stack>
#include "0.sort_test.h"
using namespace std;
#define THRESHOLD 16
#define swap(a, b) { \
	__typeof(a) __c = a; \
	a = b, b = __c; \
}

int threePointSelect(int a, int b, int c) {
	if(a > b) swap(a, b);
	if(a > c) swap(a, c);
	if(b > c) swap(b, c);
	return b;
}

struct Data {
	Data(int *arr, int l, int r) : arr(arr), l(l), r(r), code(0) {}
	int *arr, l, r;
	int pl, pr, base;
	int code;
} ;

void unguardedInsertSort(int *arr, int l, int r, int step = 1) {
    int index = l;
    for(int i = l + step; i < r; i += step) {
        if(arr[i] < arr[index]) index = i;
    }
    // swap(arr[l], arr[index]); 破坏插入排序稳定
    while(index > l) {
        swap(arr[index], arr[index - step]);
        index -= step;
    }
    for(int i = l + step; i < r; i += step) {
        index = i;
        while(arr[index] < arr[index - step]) {
            swap(arr[index], arr[index - step]);
            index -= step;
        }
    }
    return ;
}

void quickSort(int *arr, int l, int r) {
	if((r - l) <= 1) return ;
	if((r - l) == 2 && arr[l] > arr[l + 1]) {
		swap(arr[l], arr[l + 1]);
		return ;
	}
	int pl = l, pr = r - 1, base = arr[l];
	while(pl < pr) {
		while(pl < pr && arr[pr] >= base) --pr;
		if(pl < pr) arr[pl++] = arr[pr];
		while(pl < pr && arr[pl] <= base) ++pl;
		if(pl < pr) arr[pr--] = arr[pl];
	}
	arr[pl] = base;
	quickSort(arr, l, pl);
	quickSort(arr, pl + 1, r);
	return ;
}
// 直接交换
void quickSortV1(int *arr, int l, int r) {
	if((r - l) <= 2) {
		if((r - l) <= 1) return ;                    // code : 0
		if(arr[l] > arr[l + 1])  
			swap(arr[l], arr[l + 1]);
		return ;
	}
	int pl = l, pr = r - 1, base = arr[l];
	do {
		while(arr[pl] < base) ++pl;
		while(arr[pr] > base) --pr;
		if(pl <= pr) {
			swap(arr[pl], arr[pr]);
			++pl, --pr;
		}
	} while(pl <= pr);							 // code : 2
	quickSortV1(arr, l, pl);					 // code : 3
	quickSortV1(arr, pl, r);					 // code : 4
	return ;									 // code : 5
}

void non_quickSortV1(int *arr, int l, int r) {
	stack<Data> s;
	Data d(arr, l, r);
	s.push(d);
	while(!s.empty()) {
		Data &cur = s.top();
		switch (cur.code) {
			case 0 : {
				if((cur.r - cur.l) <= 2) {
					if((cur.r - cur.l) <= 1) s.pop(); // 已经弹栈了，后面要用else
					else { // caution
						if (cur.arr[cur.l] > cur.arr[cur.l + 1]) 
							swap(cur.arr[cur.l], cur.arr[cur.l + 1]);
						s.pop();
					}
				} else {
					cur.code = 1;
				}
			} break;
			case 1 : {
				cur.pl = cur.l, cur.pr = cur.r - 1, cur.base = cur.arr[cur.l];
				do {
					while(cur.arr[cur.pl] < cur.base) ++cur.pl;
					while(cur.arr[cur.pr] > cur.base) --cur.pr;
					if(cur.pl <= cur.pr) {
						swap(cur.arr[cur.pl], cur.arr[cur.pr]);
						++cur.pl, --cur.pr;
					}
				} while(cur.pl <= cur.pr);	
				cur.code = 2;	
			} break;
			case 2 : {
				Data d(cur.arr, cur.l, cur.pl);
				cur.code = 3;
				s.push(d);
			} break;
			case 3 : {
				Data d(cur.arr, cur.pl, cur.r);
				cur.code = 4;
				s.push(d);
			} break;
			case 4 : {
				s.pop();
			} break;
		}
	}
	return ;
}
// 三点取中
void quickSortV2(int *arr, int l, int r) {
	if((r - l) <= 1) return ;
	if((r - l) == 2 && arr[l] > arr[l + 1]) {
		swap(arr[l], arr[l + 1]);
		return ;
	}
	int pl = l, pr = r - 1;
	int base = threePointSelect(arr[l], arr[(r + l) / 2], arr[r - 1]);
	do {
		while(arr[pl] < base) ++pl;
		while(arr[pr] > base) --pr;
		if(pl <= pr) {
			swap(arr[pl], arr[pr]);
			++pl, --pr;
		}
	} while(pl <= pr);
	quickSortV2(arr, l, pr + 1);
	quickSortV2(arr, pl, r);
	return ;
}
// 单边递归
void quickSortV3(int *arr, int l, int r) {
	while(l < r) {
		if((r - l) <= 1) return ;
		if((r - l) == 2 && arr[l] > arr[l + 1]) {
			swap(arr[l], arr[l + 1]);
			return ;
		}
		int pl = l, pr = r - 1;
		int base = threePointSelect(
			arr[l], 
			arr[(r + l) / 2], 
			arr[r - 1]
			);
		do {
			while(arr[pl] < base) ++pl;
			while(arr[pr] > base) --pr;
			if(pl <= pr) {
				swap(arr[pl], arr[pr]);
				++pl, --pr;
			}
		} while(pl <= pr);
		quickSortV3(arr, l, pr + 1);
		l = pl;
	}
	return ;
}
// 16个元素以下， 用插入排序
void __quickSortV4(int *arr, int l, int r) {
	while((r - l) > THRESHOLD) {
		int pl = l, pr = r - 1;
		int base = threePointSelect(
			arr[l], 
			arr[(r + l) / 2], 
			arr[r - 1]
			);
		do {
			while(arr[pl] < base) ++pl;
			while(arr[pr] > base) --pr;
			if(pl <= pr) {
				swap(arr[pl], arr[pr]);
				++pl, --pr;
			}
		} while(pl <= pr);
		__quickSortV4(arr, l, pr + 1);
		l = pl;
	}
	return ;
}

void quickSortV4(int *arr, int l, int r) {
	__quickSortV4(arr, l, r);
	unguardedInsertSort(arr, l, r);
	return ;
}

int main() {
	// int *arr_small = getRandData(SMALL_DATA);
	int *arr_big = getRandData(BIG_DATA);
	// TEST(quickSort, arr_small, SMALL_DATA);
	// printf("\n");
	// TEST(quickSort, arr_big, BIG_DATA);
	// printf("\n");
	TEST(quickSortV1, arr_big, BIG_DATA);
	printf("\n");
	TEST(non_quickSortV1, arr_big, BIG_DATA);
	printf("\n");
	// TEST(quickSortV2, arr_big, BIG_DATA);
	// printf("\n");
	// TEST(quickSortV3, arr_big, BIG_DATA);
	// printf("\n");
	// TEST(quickSortV4, arr_big, BIG_DATA);
	// printf("\n");
	// free(arr_small);
	free(arr_big);
	return 0;
}

